Programmable Logic Arrays (PLAs) are commonly used for implementing Boolean logic functions in Very Large Scale Integration (VLSI) chips. With advancements in VLSI technology, it is very common to pack large and complex circuits into a single chip. For example, a typical large PLA may have as many as 66 inputs, 15 outputs, and 538 product terms, requiring 87,156 internal circuit elements (transistors, diodes, etc.). However, as gate density within the chip increases and geometry shrinks, the probability of manufacturing defects also increases. It is believed that the inability to control the number of defects limits the manufacture of larger size PLAs. Thus, a real need has existed in the industry for a method of repairing manufacturing defects in PLA chips to ensure correct circuit operation and to increase chip yield, (i.e., the percentage of usable chips manufactured).
One method presently known for repairing PLAs incorporates redundant columns or rows of circuit elements. In this method, Wey, Chang, and Vai teach the use of spare inputs, outputs, product terms, and control circuits to repair single and multiple faults. [C. Wey, T. Chang, and M. Vai, "On the Design of Fault-Tolerant Programmable Logic Arrays," International Computer Symposium, Taiwan, R.C.C. (1986).] Kuo and Fuchs teach the use of an efficient algorithm for allocation of spare columns and rows in reconfigurable processor arrays and memory units. [S. Kuo and W. Fuchs, "Efficient Spare Allocation for Reconfigurable Arrays," IEEE Design & Test of Computers, pp. 24-31 (Feb. 1987).] The disadvantage of these methods is that they require that spare columns and rows be incorporated into the chip, thus limiting the size of the usable array.
The present invention uniquely solves the problem without resort to redundant circuits. The method of the invention comprises identifying the defects within the "raw" PLA (i.e., an unprogrammed PLA which may contain manufacturing defects), reconfiguring the columns of a "mask" PLA (i.e., a mask PLA is a representation of a desired programmed PLA which exhibits the "personality" or characteristics of the PLA desired to be programmed) and mapping the mask PLA onto the raw PLA so as to mask the defects. The invention employs a method of reconfiguring physical internal elements (columns of circuit elements) within the PLA, such that the user or programmer is unaware of the reconfiguration. Since the method operates on the internal elements of the array, there is no need to alter the external programming circuitry. The method requires no spare rows or columns of array elements, and no additional hardware, but may be implemented using standard PLA testing and programming hardware. Moreover, the method provides a time efficient solution to the mapping problem, obtaining a complete solution in polynomial time of the order equal to the number of product lines cubed.